import random
import time
class Sort:
    def __init__(self,n):
        self.len = n
        self.arr=[0]*n
        self.random_data()
    def random_data(self):
        for i in range(self.len):
            self.arr[i]=random.randint(0,99)
    #快排
    def partition(self,left,right):#获取分割值下标,将最右边元素当作分割值
        k = i = left
        for i in range(left,right):
            if self.arr[i]<self.arr[right]:
                self.arr[i],self.arr[k]=self.arr[k],self.arr[i]
                k+=1
        self.arr[k],self.arr[right]=self.arr[right],self.arr[k]
        return k
    def quick_sort(self,l,r):#快排
        if l<r:
            pivot = self.partition(l, r)  # 分割值下标
            self.quick_sort(l,pivot-1)
            self.quick_sort(pivot+1,r)


    #堆排
    def adjust_max_heap(self,pos,arr_len):
        dad = pos
        son = 2*dad+1
        while son < arr_len:#左孩子小于列表长度
            if son+1 < arr_len and self.arr[son]<self.arr[son+1]:#判断右孩子存在且右孩子大于左孩子
                son += 1
            if self.arr[son]>self.arr[dad]:
                self.arr[son],self.arr[dad] = self.arr[dad],self.arr[son]
                dad = son
                son = 2*dad+1
            else:
                break
    #
    def heap_sort(self):
        #把列表整理为大根堆
        for parent in range(self.len//2 - 1, -1, -1):#从最后一位叶子结点的父结点到根节点，步长-1
            self.adjust_max_heap(parent, self.len)

        self.arr[0], self.arr[self.len-1] = self.arr[self.len-1], self.arr[0]#堆顶元素与最后一位元素交换
        for arr_len in range(self.len-1, 1, -1):
            self.adjust_max_heap(0, arr_len)
            self.arr[0], self.arr[arr_len-1] = self.arr[arr_len-1],self.arr[0]

    # def heap_sort(self):
    #     # 把列表调整为大根堆
    #     for parent in range(self.len//2 - 1, -1, -1):
    #         self.adjust_max_heap(parent, self.len)
    #     #arr = self.arr
    #     self.arr[0], self.arr[self.len-1] = self.arr[self.len-1], self.arr[0]  # 堆顶元素和最后一个元素交换
    #     for arr_len in range(self.len-1, 1, -1):
    #         self.adjust_max_heap(0, arr_len)
    #         self.arr[0], self.arr[arr_len - 1] = self.arr[arr_len - 1], self.arr[0]
    #统计时间
    def time_sort(self):
        pass

if __name__=='__main__':
    my_sort= Sort(100000)

    #print(my_sort.arr)
    #my_sort.quick_sort(0,9)
    my_sort.heap_sort()
    start_time = time.time()
    end_time = time.time()
    #print(my_sort.arr)
    print(eval("-(start_time-end_time)"))#打印堆排排序用时
